package com.MSB.XOR;

import java.util.HashMap;
import java.util.HashSet;

public class XORTest {


    /**
     * 一个数组中，有一个数出现奇数次，其他都出现偶数次。找出这个数
     * @param arr
     * @return
     */
    public int fun(int[] arr){
        int ans = 0;
        for (int i = 1; i < arr.length; i++) {
            ans = ans ^ arr[i];
        }
        return ans;
    }

    /**
     * 取出a最低位的1，
     * @param a
     * @return
     */
    public int fun1(int a){
        return a & (-a);
    }

    /**
     * 数组中有；两种数出现奇数次，其他出现偶数次，找出这两种数
     * @param arr
     * @return
     */
    public int[] fun2(int[] arr){
        int eor = 0;
        for (int j : arr) {
            eor ^= j;//eor = a ^ b;
        }
        int eor_1 = fun1(eor);//取出eor的最低位1，根据这一位是否为1
                //把数组分为两部分，一部分含a，一部分含b
        int halfEor = 0;
        for (int j : arr) {
            if ((eor_1 & j) == 0) {
                halfEor ^= j;// halfEor 为 a;
            }
        }
        int b = eor ^ halfEor;

        return new int[]{halfEor, b};
    }

    /**
     * 有1个数出现k次，其他数出现m次
     * m > 1 , m > k
     * 找出这个数
     * @param arr
     * @return
     */
    public int fun3(int[] arr, int k, int m){
        int[] t = new int[32];//t[0]代表0位置的1出现了几次
        for (int num : arr){
            for (int i = 0; i < 32; i++) {
                t[i] += (num >> i) & 1;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i] % m != 0){
                ans |= 1 << i;
            }
        }
        return ans;
    }
    public int fun3Hash(int[] arr, int k, int m){
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : arr){
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        for (int num : map.keySet()){
            if (map.get(num) == k){
                return num;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        XORTest x = new XORTest();
        int[] arr = {-1, -1, -1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4};
//        for (int i : x.fun2(arr)) {
//            System.out.println(i);
//        }

//        int[] test = randomArray(50, 2, 3);
//        for (int value : test) {
//            System.out.println(value);
//        }


        int range = 200;
        int times = 1_000_000;
        int max = 9;
        int a = (int)(Math.random() * max) + 1;
        int b = (int)(Math.random() * max) + 1;
        int k = Math.min(a,b);
        int m = Math.max(a,b);
        System.out.println("测试开始");
        for (int i = 0; i < times; i++) {
            int[] array = randomArray(range, k, m);
//            for (int value : array) {
//                System.out.println(value);
//            }

            int ans1 = x.fun3(array,k,m);
            int ans2 = x.fun3Hash(array,k,m);
            if (ans1 != ans2)
                System.out.println("出错了");
        }
        System.out.println("测试结束");
    }
    /**
     * 后面为对数器部分
     */
    public static int[] randomArray(int range, int k, int m){
        int k_val = randomByRange(range);
        int m_nums = (int)(Math.random() * 10) + 1;
        int[] array = new int[k + m * m_nums];
        int index = 0;
        for (int i = 0; i < k; i++) {
            array[i] = k_val;
            index++;
        }
        HashSet<Integer> set = new HashSet<>();
        set.add(k_val);
        while (m_nums > 0){
            int m_val;
            do{
                m_val = randomByRange(range);
            }while (set.contains(m_val));
            for (int i = 0; i < m; i++) {
                array[index++] = m_val;
            }
            set.add(m_val);
            m_nums --;
        }
        for (int i = 0; i < array.length; i++) {
            int j =  (int)(Math.random() * array.length);
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
        return array;
    }

    public static int randomByRange(int range){
        return (int)(Math.random() * range * 2) - range + 1;
    }
}
